//
// Created by 紫霄 on 2020/4/6.
//

#ifndef LEETCODE_03_H
#define LEETCODE_03_H
#include <unordered_map>
#include <vector>

class Solution {
public:
  int findRepeatNumber(std::vector<int> &nums) {
    std::unordered_map<int, int> count;
    for (auto i : nums) {
      ++count[i];
      if (count[i] > 1) {
        return i;
      }
    }
    return -1;
  }

  // 采用鸽巢原理
  int findRepeatNumber1(std::vector<int> &nums) {
    for (int i = 0; i < nums.size(); ++i) {
      while (nums[i] != i) {
        if (nums[nums[i]] == nums[i])
          return nums[i];
        int temp = nums[i];
        nums[i] = nums[temp];
        nums[temp] = temp;
      }
    }
    return -1;
  }
};
#endif // LEETCODE_03_H
